package leetcode.search;

import com.sun.deploy.util.StringUtils;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 */
public class BinaryTreePaths257 {

    class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
             this.left = left;
              this.right = right;
          }
      }

    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
        dfs( res,"", root);
        return res;
    }

    private  void dfs(List<String> res,String path,TreeNode node){
        StringBuilder sb = new StringBuilder(path);
        sb.append(node.val);

        if(node.left==null && node.right==null){
            res.add(sb.toString());
            return;
        }
        sb.append("=>");

        if(node.left!=null)
            dfs(res,sb.toString(),node.left);
        if(node.right!=null)
            dfs(res,sb.toString(),node.right);

//        curStr.remove(node.val+"");
    }


    private  List<String>  bfs(TreeNode node){
        LinkedList<TreeNode> nodeQue = new LinkedList<>();
        LinkedList<String> pathQue = new LinkedList<>();
        List<String> res = new ArrayList<>();
        nodeQue.offer(node);
        pathQue.offer(node.val+"");

        while (!nodeQue.isEmpty()){
            TreeNode poll = nodeQue.poll();
            String pollPath = pathQue.poll();

            StringBuilder  sb = new StringBuilder(pollPath);

            if(poll.left==null && poll.right==null){
                res.add(sb.toString());
                continue;
            }


            if(poll.left!=null){
                nodeQue.offer(poll.left);
                pathQue.offer(sb.append("->").append(poll.left.val).toString());

            }

            if(poll.right!=null) {
                nodeQue.offer(poll.right);
                pathQue.offer(sb.append("->").append(poll.right.val).toString());
            }
        }
        return res;
    }
}